#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <iomanip>
#include "LRU_K.h"

using namespace std;

// 修正的测试方法
class ImprovedCacheHitRateTester {
public:
    // 测试真实世界的工作负载 - 包含局部性
    static void testRealisticWorkload() {
        cout << "\n=== 真实世界工作负载测试 ===" << endl;
        
        // 场景1: 数据库查询模式（有热点表）
        vector<int> dbWorkload = generateDatabaseLikeWorkload();
        cout << "数据库查询模式 (数据范围: 1-100, 访问次数: 1000)" << endl;
        testHitRate("LRU", dbWorkload, 20);
        testHitRate("LRU-K", dbWorkload, 20, 30, 2);
        
        // 场景2: Web请求模式（有热门页面）
        vector<int> webWorkload = generateWebRequestWorkload();
        cout << "\nWeb请求模式 (数据范围: 1-200, 访问次数: 1200)" << endl;
        testHitRate("LRU", webWorkload, 25);
        testHitRate("LRU-K", webWorkload, 25, 35, 2);
        
        // 场景3: 文件访问模式（有常用文件）
        vector<int> fileWorkload = generateFileAccessWorkload();
        cout << "\n文件访问模式 (数据范围: 1-150, 访问次数: 800)" << endl;
        testHitRate("LRU", fileWorkload, 15);
        testHitRate("LRU-K", fileWorkload, 15, 25, 2);
    }
    
    // 测试包含局部性的顺序访问
    static void testLocalitySequence() {
        cout << "\n=== 局部性顺序访问测试 ===" << endl;
        
        vector<int> workload;
        random_device rd;
        mt19937 gen(rd());
        
        // 生成具有时间局部性的序列
        for (int i = 0; i < 1000; ++i) {
            // 80%的概率重复最近访问的10个数据
            if (i > 10 && (i % 100 < 80)) {
                uniform_int_distribution<> recentDis(max(1, i-10), i);
                workload.push_back(workload[recentDis(gen) % workload.size()]);
            } else {
                // 20%的概率访问新数据
                uniform_int_distribution<> newDis(1, 100);
                workload.push_back(newDis(gen));
            }
        }
        
        cout << "具有时间局部性的访问序列 (数据范围: 1-100, 访问次数: 1000)" << endl;
        testHitRate("LRU", workload, 20);
        testHitRate("LRU-K", workload, 20, 30, 2);
    }
    
    // 测试突发访问模式
    static void testBurstAccess() {
        cout << "\n=== 突发访问模式测试 ===" << endl;
        
        vector<int> workload;
        
        // 生成突发访问模式：短时间内大量访问少数数据，然后长时间访问其他数据
        for (int burst = 0; burst < 5; ++burst) {
            int hotKey = burst * 10 + 1;
            
            // 突发阶段：频繁访问热点数据
            for (int i = 0; i < 20; ++i) {
                workload.push_back(hotKey);
            }
            
            // 平稳阶段：访问其他数据
            for (int i = 0; i < 80; ++i) {
                workload.push_back(20 + burst * 20 + i % 50);
            }
        }
        
        cout << "突发访问模式 (热点数据短暂但频繁出现)" << endl;
        testHitRate("LRU", workload, 15);
        testHitRate("LRU-K", workload, 15, 25, 2);
    }

// private:
    // 生成类似数据库查询的工作负载
    static vector<int> generateDatabaseLikeWorkload() {
        vector<int> workload;
        random_device rd;
        mt19937 gen(rd());
        
        // 热点表（频繁查询）
        vector<int> hotTables = {1, 2, 3, 4, 5};
        // 普通表（偶尔查询）
        vector<int> normalTables;
        for (int i = 6; i <= 100; ++i) {
            normalTables.push_back(i);
        }
        
        for (int i = 0; i < 1000; ++i) {
            // 70%的查询集中在热点表
            if (i % 100 < 70) {
                uniform_int_distribution<> hotDis(0, hotTables.size() - 1);
                workload.push_back(hotTables[hotDis(gen)]);
            } else {
                // 30%的查询分布在普通表
                uniform_int_distribution<> normalDis(0, normalTables.size() - 1);
                workload.push_back(normalTables[normalDis(gen)]);
            }
        }
        
        return workload;
    }
    
    // 生成类似Web请求的工作负载
    static vector<int> generateWebRequestWorkload() {
        vector<int> workload;
        random_device rd;
        mt19937 gen(rd());
        
        // 热门页面
        vector<int> popularPages = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        // 普通页面
        vector<int> normalPages;
        for (int i = 11; i <= 200; ++i) {
            normalPages.push_back(i);
        }
        
        for (int i = 0; i < 1200; ++i) {
            // 60%的请求访问热门页面
            if (i % 100 < 60) {
                uniform_int_distribution<> popularDis(0, popularPages.size() - 1);
                workload.push_back(popularPages[popularDis(gen)]);
            } else {
                // 40%的请求访问普通页面（包含大量一次性访问）
                uniform_int_distribution<> normalDis(0, normalPages.size() - 1);
                workload.push_back(normalPages[normalDis(gen)]);
            }
        }
        
        return workload;
    }
    
    // 生成类似文件访问的工作负载
    static vector<int> generateFileAccessWorkload() {
        vector<int> workload;
        random_device rd;
        mt19937 gen(rd());
        
        // 常用文件
        vector<int> commonFiles = {1, 2, 3, 4, 5};
        // 临时文件（一次性访问）
        vector<int> tempFiles;
        for (int i = 6; i <= 150; ++i) {
            tempFiles.push_back(i);
        }
        
        for (int i = 0; i < 800; ++i) {
            // 50%的访问是常用文件
            if (i % 100 < 50) {
                uniform_int_distribution<> commonDis(0, commonFiles.size() - 1);
                workload.push_back(commonFiles[commonDis(gen)]);
            } else {
                // 50%的访问是临时文件（模拟大量一次性访问）
                uniform_int_distribution<> tempDis(0, tempFiles.size() - 1);
                workload.push_back(tempFiles[tempDis(gen)]);
            }
        }
        
        return workload;
    }
    
    // 保持原有的testHitRate方法
    static void testHitRate(const string& name, const vector<int>& accessSequence, int capacity) {
        LruCache<int, int> cache(capacity);
        int hits = 0;
        int value;
        
        for (int key : accessSequence) {
            if (cache.get(key, value)) {
                hits++;
            } else {
                cache.put(key, key);
            }
        }
        
        double hitRate = static_cast<double>(hits) / accessSequence.size() * 100;
        cout << name << " 命中次数: " << hits << "/" << accessSequence.size() 
             << " 命中率: " << fixed << setprecision(2) << hitRate << "%" << endl;
    }
    
    static void testHitRate(const string& name, const vector<int>& accessSequence, 
                           int mainCapacity, int historyCapacity, int k) {
        LruKCache<int, int> cache(mainCapacity, historyCapacity, k);
        int hits = 0;
        int value;
        
        for (int key : accessSequence) {
            if (cache.get(key, value)) {
                hits++;
            } else {
                cache.put(key, key);
            }
        }
        
        double hitRate = static_cast<double>(hits) / accessSequence.size() * 100;
        cout << name << " 命中次数: " << hits << "/" << accessSequence.size() 
             << " 命中率: " << fixed << setprecision(2) << hitRate << "%" << endl;
    }
};

// 专门展示LRU-K优势的测试
void demonstrateLrukAdvantage() {
    cout << "\n=== LRU-K优势展示测试 ===" << endl;
    
    // 这个测试专门设计来展示LRU-K的优势
    vector<int> workload;
    
    // 阶段1: 重复访问的热点数据
    for (int round = 0; round < 5; ++round) {
        for (int hotKey = 1; hotKey <= 10; ++hotKey) {
            workload.push_back(hotKey);  // 频繁访问前10个数据
        }
    }

    // 阶段2: 一次性访问（污染LRU缓存）
    for (int i = 11; i <= 20; ++i) {
        workload.push_back(i);  // 每个数据只访问一次
    }
    
    // 阶段3: 重复访问真正的热点数据
    for (int round = 0; round < 5; ++round) {
        for (int hotKey = 1; hotKey <= 10; ++hotKey) {
            workload.push_back(hotKey);  // 频繁访问前10个数据
        }
    }
    
    // 阶段4: 一次性访问（污染LRU缓存）
    for (int i = 21; i <= 30; ++i) {
        workload.push_back(i);  // 每个数据只访问一次
    }
    
    // 阶段5: 继续访问热点数据
    for (int round = 0; round < 5; ++round) {
        for (int hotKey = 1; hotKey <= 10; ++hotKey) {
            workload.push_back(hotKey);
        }
    }

    // 阶段6: 一次性访问（污染LRU缓存）
    for (int i = 31; i <= 40; ++i) {
        workload.push_back(i);  // 每个数据只访问一次
    }

    // 阶段7: 继续访问热点数据
    for (int round = 0; round < 5; ++round) {
        for (int hotKey = 1; hotKey <= 10; ++hotKey) {
            workload.push_back(hotKey);
        }
    }
    
    cout << "工作负载: 大量一次性访问 + 真正热点数据重复访问" << endl;
    cout << "缓存容量: LRU(10), LRU-K(主缓存10 + 历史缓存20, K=2)" << endl;
    
    ImprovedCacheHitRateTester::testHitRate("LRU", workload, 10);
    ImprovedCacheHitRateTester::testHitRate("LRU-K", workload, 10, 20, 2);
    
    cout << "\n分析: LRU会被阶段1的一次性访问污染，而LRU-K能保护热点数据！" << endl;
}

int main() {
    // 使用修正的测试方法
    ImprovedCacheHitRateTester::testRealisticWorkload();
    ImprovedCacheHitRateTester::testLocalitySequence();
    ImprovedCacheHitRateTester::testBurstAccess();
    
    // 专门展示优势的场景
    demonstrateLrukAdvantage();
    
    return 0;
}


// g++ LRUAccessHitRateTest.cpp